﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.Schemes;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;

namespace Algoritmia.Problems.Sorting
{

    public class MergeSortProblem<T> : IDivideAndConquerProblem<Lists.IList<T>>
    {
        private readonly Lists.IList<T> _list;

        public MergeSortProblem(Lists.IList<T> list)
        {
            _list = list;
        }

        #region Implementation of IDivideAndConquerProblem<T>

        public bool IsSimple
        {
            get { return _list.Count == 1; }
        }

        public Lists.IList<T> Combine(IEnumerable<Lists.IList<T>> solutions)
        {
            int i = 0, j = 0,k = 0;
            var left = solutions.First();
            var right = solutions.Last();
            var comparison = AlgoritmiaFactory.GetDefaultComparison<T>();
            var c = Enumerable.Repeat(default(T), left.Count + right.Count).ToAlgoritmiaList();
            while (i < left.Count && j < right.Count)
            {
                if (comparison(left[i], right[j]) < 0)
                {
                    c[k++] = left[i++];
                }
                else
                {
                    c[k++] = right[j++];
                }
            }
            while (i < left.Count) c[k++] = left[i++];
            while (j < right.Count) c[k++] = right[j++];
            return c;
        }

        public IEnumerable<IDivideAndConquerProblem<Lists.IList<T>>> Divide()
        {
            yield return new MergeSortProblem<T>((_list.Where((e, i) => i < _list.Count/2)).ToAlgoritmiaList());
            yield return new MergeSortProblem<T>((_list.Where((e, i) => i >= _list.Count / 2)).ToAlgoritmiaList());
        }

        public Lists.IList<T> TrivialSolution()
        {
            return _list;
        }

        #endregion
    }
     
    public class InPlaceMergeSorterProblem<T> : IDivideAndConquerProblem<InPlaceMergeSorterProblem<T>>
    {
        private readonly Lists.IList<T> list;
        private readonly int p;
        private readonly int q;
        private readonly Lists.IList<T> cache;

        public InPlaceMergeSorterProblem(Lists.IList<T> list, int p, int q, Lists.IList<T> cache)
        {
            this.list = list;
            this.p = p;
            this.q = q;
            this.cache = cache;
        }

        #region Implementation of IDivideAndConquerProblem<InPlaceMergeSorter<T>>

        public bool IsSimple
        {
            get { return q - p == 1; }
        }

        public InPlaceMergeSorterProblem<T> Combine(IEnumerable<InPlaceMergeSorterProblem<T>> solutions)
        {
            var first = solutions.First();
            var last = solutions.Last();
            var a = first.list;
            var c = first.cache;
            var comparison = AlgoritmiaFactory.GetDefaultComparison<T>();

            int i = p, j = first.q, k = p;

            while (i < first.q && j < q)
            {
                if (comparison(a[i], a[j]) < 0)
                {
                    c[k++] = a[i++];
                }
                else
                {
                    c[k++] = a[j++];
                }
            }
            while (i < first.q) c[k++] = a[i++];
            while (j < last.q) c[k++] = a[j++];

            for (i = p; i < q; i++)
            {
                a[i] = c[i];
            }
            return this;
        }

        public IEnumerable<IDivideAndConquerProblem<InPlaceMergeSorterProblem<T>>> Divide()
        {
            yield return new InPlaceMergeSorterProblem<T>(list, p, (p + q)/2, cache);
            yield return new InPlaceMergeSorterProblem<T>(list, (p + q) / 2, q, cache);
        }

        public InPlaceMergeSorterProblem<T> TrivialSolution()
        {
            return this;
        }

        #endregion
    }
}
